package stu.day39_day.day42;

public class hw2 {
    public int coinChange(int[] coins, int amount) {

        int m = coins.length;
        int[][] dp = new int[m+1][amount+1];

        for (int i=0;i<=m;i++){
            for (int j=0;j<=amount;j++){
                dp[i][j] = amount+1;
            }
        }


        dp[0][0] = 0;
        for (int i=1;i<=m;i++){
            for (int j=0;j<=amount;j++){

                if(coins[i-1]>j){
                    dp[i][j] = dp[i-1][j];
                }else {
                    dp[i][j] = Math.min(dp[i-1][j],dp[i][j-coins[i-1]]+1);
                }
            }

        }

        return dp[m][amount] == amount+1?-1:dp[m][amount];
    }



    public int change(int amount, int[] coins) {

        int m = coins.length;
        int[][] dp = new int[m+1][amount+1];

        for (int i=0;i<=m;i++){
            dp[i][0] = 1;
        }

        for (int i=1;i<=m;i++){
            for (int j=0;j<=amount;j++){

                if(coins[i-1]>j){
                    dp[i][j] = dp[i-1][j];
                }else {
                    dp[i][j] = dp[i-1][j]+dp[i][j-coins[i-1]];
                }
            }

        }

        return dp[m][amount];

    }



}
